import networkx as nx
import warnings
import copy
from queue import Queue
from collections import deque
from .misc import is_regular_nonterminal, is_regular_terminal


EMPTY = 'ε'

class Production:
    def __init__(self, dat: str, delimeter=None):
        self.production = []
        if delimeter is None:
            for ch in dat:
                self.production.append(ch)
        else:
            self.production = dat.split(delimeter)
            
        if '' in self.production:
            warnings.warn('there is empty string character in this production, maybe you have consecutive delimeters in this production, it will be autoremoved\n production: {}'.format(dat))
            self.production = list(filter(lambda x: x!='', self.production))
        
        if EMPTY in self.production and len(self.production) > 1:
            raise Exception('invalid empty symbol usage, production: {}'.format(dat))
        

        # self.production = list(set(self.production))

    def __iter__(self):
        return self.production.__iter__()

    def __str__(self):
        return "".join(self.production)

    def __getitem__(self, key):
        return self.production[key]

    def __contains__(self, key):
        return self.production.__contains__(key)

    def __eq__(self, other):
        if not len(self.production) == len(other.production):
            return False

        for index, item in enumerate(self.production):
            if self.production[index] != other.production[index]:
                return False

        return True

    def subarray(self, l, r):
        return self.production[l:r]


    def remove(self, key):
        '''
        completely remove a character in this production
        '''
        while key in self.production:
            self.production.remove(key)

    def pop(self, index=-1):
        '''
        like list.pop()
        '''

        self.production.pop(index)

    def empty(self):
        '''
        return if this production is empty
        '''
        return len(self.production) == 0

    def eq(self, string):
        '''
        return if this production is equal to a string expression
        '''
        if len(string) != len(self.production):
            return False
        for index, ch in enumerate(Production):
            if string[index] != ch:
                return False
        return True

    def __len__(self):
        return len(self.production)

    def __hash__(self):
        val = 0

        for index, item in enumerate(self.production):
            val ^= index * item.__hash__()


        return val


    

class Entry:

    def __init__(self, nt: str, productions=[]):
        self.nt = nt
        self.productions = productions
        self.productions = list(set(self.productions))
        pass

    def concat(self, entry):
        self.productions += entry.productions
        self.productions = list(set(self.productions))

    def __iter__(self):
        return self.productions.__iter__()

    def __str__(self):
        if len(self.productions) == 0:
            print("empty set for {}".format(self.nt))
        str_list = [str(p) for p in self.productions]
        str_list.sort()
        return "{} -> {}".format(self.nt, "|".join(str_list))
    
    def __getitem__(self, key):
        return self.productions[key]

    def __contains__(self, key):
        for p in self.productions:
            if key in p:
                return True        
        return False

    def empty(self):
        return len(self.productions) == 0
    
    def remove_symbol(self, sym):
        '''
        remove a symbol in all productions in this entry
        '''
        for prod in self.productions:
            prod.remove(sym)
            if prod.empty():
                self.productions.remove(prod)
    
    def remove_production(self, production):
        '''
        remove a production in this entry, will remove only single one if contains multiple same production
        '''

        self.productions.remove(production)

    

    pass

class Grammar:
    def __init__(self, start_state='S', entrys=dict()):
        self.entry = entrys
        self.start_state = start_state
        self.nt = set()
        self.t = set()
        self.compiled = False

    def add_entry(self, entry: Entry):
        '''
        add a single entry
        '''
        nt = entry.nt
        if nt in self.entry:
            self.entry[nt].concat(entry)
        else:
            self.entry[nt] = entry

        self.compiled=False

    def __str__(self):
        return '===================\ngrammar:\n{}\n==================='.format('\n'.join([str(entry) for entry in self.entry.values()]))

    def __iter__(self):
        return self.entry.values().__iter__()

    def __getitem__(self, key):
        return self.entry[key]
    
    def __contains__(self, key):
        return self.entry.__contains__(key)


class ContextFreeGrammar(Grammar):
    def __init__(self, start_state='S', entrys=dict()):
        super().__init__(start_state=start_state, entrys=entrys)
        self.first = dict()
        self.follow = dict()
        self.compiled = True

    @staticmethod
    def is_regular_nonterminal(ch):
        if len(ch) == 1 and ((ch.isalpha() and ch.upper() == ch) or ch.isdigit()):
            return True
        for c in ch:
            if ord(c) >= ord('0') and ord(c) <= ord('9'):
                return False
        if len(ch) > 1 and ch == ch.lower():
            return True
        return False

    @staticmethod
    def is_regular_terminal(ch):
        if len(ch) == 1 and not ContextFreeGrammar.is_regular_nonterminal(ch):
            return True
        return False

    def is_well_formed(self):
        '''
        check if this grammar is well informed
        non-terminals should be either a lower-case word or a single upper-case alphabet. digits shouldn't appear in a non-terminal.

        terminals should be a single char, and it also shouldn't be a non-terminal

        examples:

        1 -- terminal

        abc -- non-terminal

        A -- non-terminal

        a -- terminal

        '''
        for ch in self.nt:
            if not is_regular_nonterminal(ch):
                return False
        for ch in self.t:
            if not is_regular_terminal(ch):
                return False
        return True

    def regular_infer(self):
        '''
        infer every character in this grammar, nt = entry.keys and t is the others
        '''

        if not self.is_well_formed():
            raise Exception(
                "this grammar is not well-formed, so it's dangerous for this program to analysis this grammar")
        self.nt = set(self.entry.keys())
        for entry in self.entry.values():
            for production in entry.productions:
                for ch in production:
                    if not ch in self.nt:
                        if ContextFreeGrammar.is_regular_nonterminal(ch):
                            self.nt.add(ch)
                        else:
                            self.t.add(ch)

        self.compiled = True


    def make(self, t, nt):
        '''
        specify non-terminals and terminals in this grammar
        '''
        
        self.t = t
        self.nt = nt

        s1 = set(t)
        s2 = set(nt)
        if (len(s1 & s2) > 0):
            raise Exception('there is intersection with terminals and non-terminals')

        for nont in nt:
            if not nont in self.entry:
                warnings.warn('{} is not expanding, thus useless'.format(nont))
            self.entry[nont] = Entry(nont)

        pass


    def eliminate_useless_symbols(self):
        r'''
        eliminate this grammar's useless symbol, change is inplace
        '''

        q = Queue()
        reachable = set()
        q.put(self.start_state)
        reachable.add(self.start_state)

        to_delete = []
        while not q.empty():
            now = q.get()
            if not now in self.entry:
                to_delete.append(now)
                continue
            entry = self.entry[now]
            for prod in entry:
                for sym in prod:
                    if sym in self.nt and not sym in reachable:
                        reachable.add(sym)
                        q.put(sym)
        self.nt = set(self.entry.keys()) - set(to_delete)
        for sym in self.nt:
            if not sym in reachable or self.entry[sym].empty():
                to_delete.append(sym)
        
        for sym in self.nt:
            
            entry = self.entry[sym]
            for del_sym in to_delete:
                entry.remove_symbol(del_sym)

        return to_delete
        pass

    def infer_nullable(self):
        '''
        check for each of non-terminals if it is nullable
        '''
        self.is_nullable = set()
        update = True
        while update:
            update = False
            for nt in self.nt:
                if nt in self.is_nullable:
                    continue
                for prod in self.entry[nt]:
                    if EMPTY in prod:
                        self.is_nullable.add(nt)
                        update = True
                        break
                    infer = True
                    for ch in prod:
                        if ch in self.t:
                            infer = False
                            break
                        else:
                            if not ch in self.is_nullable:
                                infer = False
                                break
                    if infer:
                        self.is_nullable.add(nt)
                        update = True
                        break
        
        # print(self.is_nullable)

        self.is_nullable = list(self.is_nullable)
        self.is_nullable.sort()
        pass

    

    def eliminate_eps_production(self):
        r'''
        eliminate eps production
        '''
        for nt in self.nt:
            self.entry[nt].remove_symbol(EMPTY)
            # continue
            
            nentry_list = []
            for prod in self.entry[nt]:
                a = []
                
                for i, ch in enumerate(prod):
                    if ch in self.is_nullable:
                        a.append((ch, i))

                n = len(a)
                for mask in range(2**n):
                    nprod = copy.deepcopy(prod)
                    dcnt = 0
                    for j in range(n):
                        if (mask >> j) & 1 == 0:
                            nprod.pop(a[j][1] - dcnt)
                            dcnt += 1
                            # nprod.remove(a[j][0])
                            pass
                    if len(nprod) > 0:
                        nentry_list.append(nprod)

            # self.entry[nt].remove_production(prod)
            # self.entry[nt].concat(nentry)
            nentry_list = list(set(nentry_list))
            self.entry[nt] = Entry(nt, nentry_list)
        pass

    def eliminate_cycle_produciton(self):
        r'''
        eliminate cycle production
        '''

    def __try_new_nt(self):
        for i in range(26):
            ch = chr(ord('A') + i)
            if not ch in self.nt:
                return ch

        raise Exception("No more not used non-terminals")


    def eliminate_left_recursion1(self):
        r'''
        remove all A -> Aabc... 
        '''

        nd = dict()

        for nt, entry in self.entry.items():
            alpha = []
            beta = []
            for prod in entry:
                if prod.subarray(0, 1)[0] == nt:
                    alpha.append(prod.subarray(1, len(prod)))
                else:
                    beta.append(prod.production)
            if len(alpha) > 0:
                nnt = self.__try_new_nt()
                nlist = [Production("".join(s) + nnt) for s in alpha] + [Production("".join(s)) for s in alpha]
                self.nt.add(nnt)
                nd[nnt] = Entry(nnt, nlist)
                nd[nt] = Entry(nt, [Production("".join(b) + nnt) for b in beta])
                
        
        for k, v in nd.items():
            self.entry[k] = v

    
    def left_factoring1(self):


        raise Exception("Not impl")


        def prefixs(s: str) -> list:
            res = []
            for i in range(len(s)):
                res.append(s[0:i+1])
            return res
        
        
        nd = dict()
        for nt, entry in self.entry.items():
            mp = dict()
            
            for index, prod in entry.items():
                # ps = prefixs(prod.producti)
                pass
        pass



    def eliminate_left_recursion_without_cycles(self):
        r'''
        do not use
        '''
        raise Exception("No impl")
        G = nx.MultiDiGraph()

        for nt in self.nt:
            self.first[nt] = set()
            print('entry', self.entry[nt].__class__)
            
            entry = self.entry[nt]
            
            for prod in entry:
                print('prod', prod)
                if prod[0] in self.t:
                    self.first[nt].add(prod[0])
                else:
                    assert prod[0] in self.nt, "unrecognized charactor {}".format(prod[0])
                    print('add_edge', nt, prod[0])
                    G.add_edge(nt, prod[0])
            print('first', self.first[nt])
        print(G.edges)
        print(G.nodes)

        print(G.in_degree)

        try:
            print(list(nx.topological_sort(G)))
        except Exception as e:
            print('fail')
        pass



    def left_most_derivation(self, string):
        res = []
        for ch in string:
            res.append(ch)
            update = True
            while update:
                update = False
                for nt, entry in self.entry.items():
                    for production in entry:
                        if production.eq(string):
                            for i in len(string):
                                res.pop()
                            res.append(nt)
                            update = True
                            break
                    if update:
                        break
        return ''.join(res)

        pass

    def preprocess(self):
        r'''
        some preprocess steps: regular_infer(), eliminate_useless_symbols, infer_nullable()
        '''
        self.regular_infer()
        self.eliminate_useless_symbols()
        self.infer_nullable()

def test():
    def arithmetic_expression():
        g = ContextFreeGrammar()
        g.add_entry(
            Entry('expression', [Production('expression + term', ' ')]))
        g.add_entry(
            Entry('expression', [Production('expression - term', ' ')]))
        g.add_entry(Entry('expression', [Production('term', ' ')]))
        g.add_entry(Entry('term', [Production('term * factor', ' ')]))
        g.add_entry(Entry('term', [Production('term / factor', ' ')]))
        g.add_entry(Entry('term', [Production('factor', ' ')]))
        g.add_entry(Entry('factor', [Production('( expression )', ' ')]))
        g.add_entry(Entry('factor', [Production('id', ' ')]))

        return g
    print('[1]: print the grammar of airthmetic_expression')
    g=arithmetic_expression()
    print(g)

    entry=g.entry['expression']
    print('[2]: print the productions of {}'.format(entry))
    for prod in entry:
        print(prod)

    print('[3]: print the entries of arithmetic_expression')
    for entry in g:
        print(entry)


    print('[4] if g is well-formed')
    print(g.is_well_formed())


    print('[5] if factor is a terminal in Grammar')
    print('factor' in g)
    e = g['factor']

    print('[6] if expression is in g["factor"]')
    print('expression' in e)



def main():
    test()
if __name__ == "__main__":
    main()
